package insertsort;

import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * 各种排序算法
 * @Author tongchen
 * @Date 2022-11-08
 */
public class Sort {
    //编写基数排序
    public static void baseSort(int[]arr){

        //遍历数组找最大值
     int max=findMax(arr);
     int min=findMin(arr);
     //求差值
        int sub=max-min+1;
        //建立数组
        int []num=new int[sub];
        //循环放入
        int index=0;
        for(int i=0;i<arr.length;++i){

            num[arr[i]-min]++;
        }
        //输出
        for(int i=0;i< num.length;++i){
            while(num[i]!=0){
                num[i]--;
                arr[index++]=i+min;
            }

        }

    }

    private static int findMin(int[] arr) {
        int min=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(min>arr[i]){
                min=arr[i];
            }
        }
        return min;
    }

    private static int findMax(int[] arr) {
        int max=arr[0];
        for(int i=1;i<arr.length;++i){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        return max;
    }

    //编写双指针选择排序
    public static void selectSort1 (int[] array) {
        //从第一个数进行排序
            int left=0;
            int right= array.length-1;
            while(left<right){
                int minIndex=left;
                int maxIndex=left;
                minIndex = findMinIndex(minIndex, right,array);
                maxIndex=findMaxIndex(maxIndex,right,array);
                if(minIndex!=left){
                    swap(array,minIndex,left);
                }
                if(maxIndex==left){
                    maxIndex=minIndex;
                }
                if(maxIndex!=right){
                    swap(array,right,maxIndex);
                }
                left++;
                right--;
            }
    }

    private static int findMaxIndex(int maxIndex,int end,int[]arr) {
        //开始循环
        for(int i=maxIndex+1;i<=end;++i){
            if(arr[maxIndex]<arr[i]){
                maxIndex=i;
            }
        }
        return maxIndex;

    }

    //编写选择排序
    public static void selectSort (int[] array) {
      //从第一个数进行排序
        for(int i=0;i< array.length;++i){
            //定义最小值下标
            int minIndex=i;
            minIndex = findMinIndex(minIndex, array.length-1,array);
            if(minIndex!=i){
                swap(array,minIndex,i);
            }
        }
    }

    private static void swap(int[] array, int minIndex, int minIndex1) {
        int temp=array[minIndex];
        array[minIndex]=array[minIndex1];
        array[minIndex1]=temp;
    }

    private static int findMinIndex(int minIndex,int end,int []arr) {
        for(int i=minIndex+1;i<=end;++i){
            if(arr[minIndex]>arr[i]){
                minIndex=i;
            }
        }
        return minIndex;
    }

    //测试时间
    public static int testTimeInsert( int[]arr){
        //记录开始时间
        long begin = System.currentTimeMillis();
        //进行排序
        insertSort(arr);
        long end = System.currentTimeMillis();
        return (int)(end-begin);
    }
    public static int testTimeShell( int[]arr){
        //记录开始时间
        long begin = System.currentTimeMillis();
        //进行排序
        shellSort(arr);
        long end = System.currentTimeMillis();
        return (int)(end-begin);
    }
    public static int testTimeSelect( int[]arr){
        //记录开始时间
        long begin = System.currentTimeMillis();
        //进行排序
        selectSort(arr);
        long end = System.currentTimeMillis();
        return (int)(end-begin);
    }
    public static int testTimeSelest1( int[]arr){
        //记录开始时间
        long begin = System.currentTimeMillis();
        //进行排序
        selectSort1(arr);
        long end = System.currentTimeMillis();
        return (int)(end-begin);
    }
    //创建随机数数组
    public static int[] createInt(){
        int[]arr=new int[CAPACITY];
        Random random = new Random();
        for (int i=0;i<arr.length;++i){
            arr[i]=random.nextInt(CAPACITY);
        }
        return arr;
    }
    //定义数组默认容量
    private final static int CAPACITY=1_00000;

    /**
     * 插入排序
     * 时间复杂度：最坏的情况：O(N^2)， 最好的情况已经有序且符合排序规则O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     *      提示：一个稳定的排序可以变成不稳定的，但一个本身不稳定的排序是不可能变成稳定的
     * @param array
     */
    public static void insertSort (int [] array) {
        for(int i=1;i< array.length;++i){
            int j=i-1;
            //将要比较的数进行储存
            int temp=array[i];

            while(j>=0){
                if(array[j]>temp){
                    array[j+1]=array[j];
                    j--;
                }
                else {

                    break;
                }
            }
            array[j+1]=temp;
        }

    }
    //归并排序的第二种实现方法（使用迭代）
    public static void mergeSortItr(int[]arr){
        //定义步长
        int gap=1;
        while(gap<arr.length){
            for(int i=0;i<arr.length;i+=2*gap){
                //【0.i+2*gap】范围内为一个归并排序的范围
                //定义left mid right下标
                int left=i;
                int mid=i+gap-1;
                int right=mid+gap;
                //修正中间值和右节点的下标
                if(mid> arr.length-1){
                    mid=arr.length-1;
                }
                if(right>arr.length-1){
                    right= arr.length-1;
                }
                merge(arr,left,mid,right);
            }

            gap*=2;
        }


    }

    //归并排序的第一种实现思路（使用递归）
    public static void mergeSort(int []arr,int left,int right){
        //检查下标的合法性
        if(left>=right){
            return;
        }
        //建立中间结点
        int middle=(left+right)/2;
        //对数组进行划分
        mergeSort(arr,left,middle);
        mergeSort(arr,middle+1,right);
        //合并数组
        merge(arr,left,middle,right);
    }

    private static void merge(int[] arr, int left, int middle, int right) {
        //创建临时数组
        int []temp=new int[right-left+1];
        int index=0;
        int begin1=left;
        int end1=middle;
        int begin2=middle+1;
        int end2=right;
        while(begin1<=end1&&begin2<=end2){
            if(arr[begin1]<=arr[begin2]){
                temp[index++]=arr[begin1++];
            }
            else {
                temp[index++]=arr[begin2++];
            }
        }
        while(begin1<=end1){
            temp[index++]=arr[begin1++];
        }
        while(begin2<=end2){
            temp[index++]=arr[begin2++];
        }
        //修改原有数组

        for(int i=0;i<(right-left+1);++i){
            arr[left+i]=temp[i];
        }
    }

    //冒泡排序的实现
    public static void bubbleSort(int[]arr){
        for(int i=0;i< arr.length-1;++i){
            for (int j = 0; j < arr.length-i-1 ; j++) {
            if(arr[j]>arr[j+1]){
                swap(arr,j,j+1);
            }
            }
        }
    }
    //快速排序的迭代实现
    public static void quickItor(int[]arr) {
        //确定数组的左值和右值
        int left = 0;
        int right = arr.length - 1;
        //建立辅助栈
        Stack<Integer> stack = new Stack<>();
        //寻找中间结点
        int len = quickSortCore(arr, left, right);
        //判断左右是否只剩一个结点
        if (left < len - 1) {
            //左半部分入栈
            stack.push(left);
            stack.push(len - 1);
        }
        if (right>len + 1) {
            //右半部分入栈
            stack.push(len + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            len = quickSortCore(arr, left, right);
            //判断左右是否只剩一个结点
            if (left <len - 1) {
                //左半部分入栈
                stack.push(left);
                stack.push(len - 1);
            }
            if (right > len + 1) {
                //左半部分入栈
                stack.push(len + 1);
                stack.push(right);
            }
        }
    }
    //利用三树取中法，解决快速排序中的栈溢出问题
    public static int swapMiddle(int []arr,int left,int right){
        //寻找中间下标的值
        int middle=(left+right)/2;
        //对数组的左右大小关系进行判断
        if(arr[left]>arr[right]){
            if(arr[middle]>arr[left]){
                return left;
            }
            else if(arr[middle]<arr[right]){
                return right;
            }
            else{
                return middle;
            }
        }
        else {
            if(arr[middle]<arr[left]){
                return left;
            }
            else if(arr[middle]>arr[right]){
                return right;
            }
            else{
                return middle;
            }
        }
    }
    //快速排序的实现（使用第一种方法：前后交换）
    public static void quickSort(int[]arr,int left,int right){
        //定义终止条件
        while(left>=right){
            return;
        }
        //对数组进行调整(使其达到非顺序的数组)
        int mid=swapMiddle(arr,left,right);
        swap(arr, left, mid);
        //int len=quickSortCore(arr,left,right);
        int len=quickSortCoreDig(arr,left, right);
        //递归左部分
        quickSort(arr,left,len-1);
        //递归右部分
        quickSort(arr,len+1,right);

    }
//快速排序的核心1
    private static int quickSortCore(int[] arr, int left, int right) {
        //定义中间结点
        int midIndex=left;
        while(left<right){
            //right坐标向左走
            while(left<right&&arr[midIndex]<=arr[right]){
                right--;
            }
            while(left<right&&arr[midIndex]>=arr[left]){
                left++;
            }
            //进行交换

            swap(arr,left,right);
        }
        //将中间结点和right结点进行交换

        swap(arr,midIndex,right);

        return right;
    }
    public static int quickSortCoreDig(int[]arr,int left,int right){
        //将中间结点保存起来
        int mid=arr[left];
        //保证左节点一直在右结点的右侧
        while(left<right){
            //右结点一直向左不断遍历,直到找到比基准值小的值
            while(right>left&&arr[right]>=mid){
                right--;
            }
            //将右结点的值放入左节点内
            arr[left]=arr[right];
                //左结点一直向右不断遍历,直到找到比基准值大的值
                while(right>left&&arr[left]<=mid){
                    left++;
                }
                //将右结点的值放入左节点内
                arr[right]=arr[left];
        }
        //当左右节点相遇时,将基准值放入
        arr[left]=mid;
        return left;
    }

    public static void shellSort (int[] array) {
        //将整个数组进行分组，将分组的小数组分别进行排序，直到分组数为1进行最后一次排序
        int gap= array.length/2;
        while(gap>0){
            shell(array,gap);
            gap/=2;
        }
    }

    private static void shell(int[] array, int gap) {
    //定义外层循环(不断增加排序的数量)
        for(int i=gap;i< array.length;++i){
            //将要比较的数字进行储存
            int temp=array[i];
            int j=i-gap;
            while(j>=0){
                if(array[j]>temp){
                    array[j+gap]=array[j];
                    j=j-gap;
                }
                else {
                    break;
                }
            }
            array[j+gap]=temp;
        }
    }


    public static void main(String[] args) {

        int[]arr={9,8,7,6,4,5,3,2,1};//5655????
        //mergeSort(arr,0, arr.length-1);
       // mergeSortItr(arr);
        //使用基数排序
        //baseSort(arr);
        //使用冒泡排序
       // bubbleSort(arr);
   //  quickSort(arr,0,arr.length-1);
        quickItor(arr);
     System.out.println(Arrays.toString(arr));
//        int[] anInt = createInt();
//        System.out.println("插入排序 "+testTimeInsert(anInt));
//        System.out.println("shell排序 "+testTimeShell(anInt));
//        System.out.println("选择排序 "+testTimeSelect(anInt));
//        System.out.println("选择排序1 "+testTimeSelest1(anInt));

    }
}
